package 动态规划;

import org.junit.Test;

/**
 * @description: 0-1背包
 *  给你一个可装载重量为 W 的背包和 N 个物品，每个物品有重量和价值两个属性。
 *  其中第 i 个物品的重量为 wt[i]，价值为 val[i]，现在让你用这个背包装物品，最多能装的价值是多少？
 * @author: shuai.chen@shuyun.com
 * @date: 2023/2/7 12:43 PM
 */
public class ZeroPackage02 {

    @Test
    public void test01(){
        // 定义
        int W = 15;
        int[] wt = {2, 2, 1, 12, 7};
        int[] val = {6, 2, 10, 3, 1};
        // 运行
        int maxValue = countMaxValue(W, wt, val);
        System.out.println(maxValue);
    }

    /**
     * 动态规划 解法1
     * @param W
     * @param wt
     * @param val
     * @return
     */
    public int countMaxValue(int W, int[] wt, int[] val){
        int N = wt.length;

        int[][] dp = new int[N + 1][W + 1];


        /*
            dp[2][5] = 6;
            表示 对于前2个物品, 当前背包的容量为5, 可以装下的最大价值为6。

            dp[i][w]
            把第i个放入背包：
                第i-1个容量 w - wt[i-1]
                dp[i][w] = val[i-1] + dp[i-1][w - wt[i-1]]
            不放第i个：
                dp[i][w] = dp[i-1][w]
         */

        // 两个状态
        for (int i = 1; i <= N; i++) {  // 物品的所有取值  1 ... N
            for (int w = 1; w <= W; w++) {  // 可装容量的所有取值  1 ... W
                if (w - wt[i-1] < 0) {
                    // 不装入
                    dp[i][w] = dp[i-1][w];
                } else {
                    // 装入或不装入, 择优
                    dp[i][w] = Math.max(
                            val[i - 1] + dp[i - 1][w - wt[i - 1]],
                            dp[i - 1][w]
                    );
                }
            }
        }


        return dp[N][W];
    }

    /**
     * 动态规划 解法2
     *
     * @param W
     * @param wt
     * @param val
     * @return
     */
    public int countMaxValue2(int W, int[] wt, int[] val){

        return 1;
    }

}
